/**
 * @file csim.c
 * @author TXG
 * @brief 一个模拟cache, 重现内存的追踪, 输出hit, miss, eviction的次数, 替换策略为LRU
 * @version 0.3
 * @date 2021-04-29
 * 
 * @copyright Copyright (c) 2021
 * 
 * 实现和假设:
 *  1. 每一条访存(load/store : L/S)指令最多引起cache的一次miss
 *  2. 加载指令(I)被忽略, 因为只关心data cache的表现
 *  3. 数据修改(M)被视作对同一地址的cache行先store后load(S & L) 
 *     该操纵将导致2次hit, 或1次miss与1次hit和1次可能的eviction
 * 
 * 说明:
 *  1. 函数printSummary()来自于头文件cachelab.h
 *     用以打印输出hit, miss, eviction的次数
 *  2. 使用提供的脚本测试模拟cache的性能
 * 
 */

/************************************* 宏定义 *************************************/

// #define DEBUG
#define USE_CACHELAB_H
#define USE_GETOPT_H

/************************************* 头文件 *************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#ifdef USE_GETOPT_H
    #include <getopt.h>
#endif
#ifdef USE_CACHELAB_H
    #include "cachelab.h"
#endif

/********************************** 数据结构定义 **********************************/

/* 内存地址 : |tag|index|offset| */
typedef unsigned long long int memAddr;

/* cache行 */
typedef struct cacheLine {
    char valid;                     // 有效位
    memAddr tag;                    // 组号
    unsigned long long int count;   // LRU算法替换依据, hit减1, 其余情况自增1
} cacheLine;

/* cache组 */
typedef cacheLine* cacheSet;    // 一个组内的多个行

/* cache */
typedef cacheSet* myCache;      // 一个cache内有多个组

/************************************ 全局变量 ************************************/

/* 命令行参数解析 */
int verbosity = 0;          // 可选冗余标志, 打印追踪信息
int s = 0;                  // 索引位数
int b = 0;                  // 块偏移位数
int E = 0;                  // 每组的行数 : ?-组相联
char* traceFile = NULL;     // trace文件路径

/* cache参数 */
int S;                      // 组数 : S = 2 ^ s
int B;                      // 块大小(bytes) : B = 2 ^ b, 然而并没有用上

/* cache性能描述的计数器 */
int hitCount = 0;           // hit数
int missCount = 0;          // miss数
int evictionCount = 0;      // eviction数

/* 模拟cache */
myCache cache;              // cache对象
memAddr setIndexMask;       // 从内存地址中获取cacheSet的index掩码

/************************************ 过程函数 ************************************/

/**
 * @brief 打印帮助文档
 * 
 * @param argv 命令行参数
 */
void printHelp(char* argv[]) {
    printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0]);
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n");
    printf("\nExamples:\n");
    printf("  linux>  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]);
    printf("  linux>  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]);
}

/**
 * @brief 初始化模拟cache
 *        申请内存空间, 对valid, tag和count置0, 计算setIndexMask
 */
void initialCache() {
    cache = (cacheSet*)malloc(sizeof(cacheSet) * S);
    for(int i = 0; i < S; ++i) {
        cache[i] = (cacheLine*)malloc(sizeof(cacheLine) * E);
        for(int j = 0; j < E; ++j) {
            cache[i][j].valid = 0;
            cache[i][j].tag = 0;
            cache[i][j].count = 0;
        }
    }
    setIndexMask = (memAddr)(pow(2, s) - 1);       // mask为有s-1位1的二进制数
}

/**
 * @brief free申请的内存空间
 * 
 */
void freeCache() {
    for(int i = 0; i < S; ++i) {
        free(cache[i]);             // free每个set的line
    }
    free(cache);
}

/**
 * @brief 通过内存地址访存数据
 *        若数据已存在, hit数加1
 *        若数据不存在, 将其加载进cache, miss数加1
 *        若有cache行被替换, eviction数加1
 * @param addr 内存地址
 */
void accessCache(memAddr addr) {

    /* 根据已有信息得到index, tag和cache组 */
    memAddr setIndex = (addr >> b) & setIndexMask;
    memAddr tag = addr >> (s + b);
    cacheSet cacheSet = cache[setIndex];

    /* 标记是否命中 */
    int isHit = 0;

    /* 遍历cache组内的行 */
    for(int i = 0; i < E; ++i) {
        if(tag == cacheSet[i].tag && cacheSet[i].valid == 1) {
            // hit
            ++hitCount;
            if(verbosity) printf(" hit");
            cacheSet[i].count = 0;
            isHit = 1;
        }
        else {
            cacheSet[i].count += 1;
        }
    }

    /* miss处理 */
    if(isHit != 1) {
        // miss
        ++missCount;
        if(verbosity) printf(" miss");
        int index = 0;                          // 遍历组内行的下标
        int evictionIndex = 0;                  // 被替换的行
        int outOfDataCount = cacheSet[0].count; // 记录要被替换行的count

        for(index = 0; index < E; ++index) {
            // 载入数据
            if(cacheSet[index].valid == 0) {
                cacheSet[index].valid = 1;
                cacheSet[index].tag = tag;
                cacheSet[index].count = 0;
                break;
            }
            // 更新可能被替换的行和最大的count
            if(outOfDataCount < cacheSet[index].count) {
                evictionIndex = index;
                outOfDataCount = cacheSet[index].count;
            }
        }
        if(index >= E) {
            // eviction
            ++evictionCount;
            if(verbosity) printf(" eviction");
            cacheSet[evictionIndex].valid = 1;
            cacheSet[evictionIndex].tag = tag;
            cacheSet[evictionIndex].count = 0;
        }
    }
}

/**
 * @brief 将字符串中的空格去除
 * 
 * @param strSrc 被操作并被修改的源字符串
 */
void removeSpace(char* strSrc) {
    char* strDes = (char*)malloc(strlen(strSrc) + 1);
    if(strSrc[0] != ' ') {
        strcpy(strDes, &strSrc[0]);
    }
    else {
        strcpy(strDes, &strSrc[1]);
    }
    strcpy(strSrc, strDes);
}

/**
 * @brief 使用cache重现内存的追踪
 * 
 * @param traceFilename trace文件路径
 */
void doTrace(char* traceFilename) {
    char buffer[1024];                              // 缓冲区
    memAddr addr = 0;                               // 地址
    unsigned int size = 0;                          // 访问的内存字节数量
    char operation;                                 // 操作(I/L/S/M)
    FILE* traceFilePointer = fopen(traceFile, "r"); // trace文件指针, 只读打开文件

    /* 处理文件内容 */
    while(1) {
        char* readLine = fgets(buffer, sizeof(char) * 1023, traceFilePointer);    // 读一行
        if(readLine == NULL) {                      // 文件尾
            break;
        }
        else {
            readLine[strlen(readLine) - 1] = '\0';      // 有效字符串
            removeSpace(readLine);                      // 去除空格
            sscanf(buffer, "%c%llx%d", &operation, &addr, &size);   // 拆分字符串得到相关参数
            #ifdef DEBUG
                printf("readLine: %s, operation: %c, addr: %llx, size: %d", 
                        readLine, operation, addr, size);
            #endif
            if(operation == 'L' || operation == 'S') {
                if(verbosity) printf("%s", readLine);
                accessCache(addr);
            }
            else if(operation == 'I') {
                continue;
            }
            else if(operation == 'M') {
                if(verbosity) printf("%s", readLine);
                accessCache(addr);
                accessCache(addr);
            }
        }
        if(verbosity) printf("\n");
    }
    fclose(traceFilePointer);
}

/*********************************** main函数 ***********************************/

/**
 * @brief 运行模拟cache
 * 
 * @param argc 参数个数
 * @param argv 参数
 * @return int 0 -> 正常退出, 1 -> 异常退出
 */
int main(int argc, char* argv[]) {
    
    /* 处理参数 */
    #ifdef USE_GETOPT_H
        char c;
        while((c = getopt(argc, argv, "s:E:b:t:vh")) != -1) {
            switch(c) {
            case 's':               // 索引位数
                s = atoi(optarg);
                break;
            case 'E':               // 每组的行数
                E = atoi(optarg);
                break;
            case 'b':               // 块偏移位数
                b = atoi(optarg);
                break;
            case 't':               // 文件
                traceFile = optarg;
                break;
            case 'v':               // 可选冗余标志
                verbosity = 1;
                break;
            case 'h':               // 帮助文档
                printHelp(argv);
                return 0;
            default:
                printHelp(argv);
                return 1;
                break;
            }
        }
    #else   // 这种参数解析方式可能会引起 Segmentation fault (core dumped), 默认了参数输入顺序
        for(int i = 1; i < argc; ++i) {
            char* arg = *(argv + i);			// 获取当前参数
		    char* nextArg = *(argv + i + 1);	// 获取下一参数
		    if(strcmp(arg, "-h") == 0) {		// 帮助文档
		    	printHelp(argv);
                return 0;
		    }
		    else if(strcmp(arg, "-v") == 0) {	// 可选冗余标志
		    	verbosity = 1;
		    }
		    else if(strcmp(arg, "-s") == 0) {	// 索引位数
		    	s = atoi(nextArg);
		    	++i;
		    }
		    else if(strcmp(arg, "-E") == 0) {	// 每组的行数
		    	E = atoi(nextArg);
		    	++i;
		    }
		    else if(strcmp(arg, "-b") == 0) {	// 块偏移位数
		    	b = atoi(nextArg);
		    	++i;
		    }
		    else if(strcmp(arg, "-t") == 0) {	// 文件
		    	traceFile = nextArg;
		    	++i;
		    }
    }
    #endif

    /* 所需参数无效 */
    if (s == 0 || E == 0 || b == 0 || traceFile == NULL) {
        printf("%s: Missing required command line argument\n", argv[0]);
        printHelp(argv);
        return 1;
    }

    /* 通过s, b计算S, B */
    S = (unsigned int)pow(2, s);
    B = (unsigned int)pow(2, b);    // 这个参数并没有使用, 没有实际数据装入cache

    /* 初始化cache */
    initialCache();
    #ifdef DEBUG
        printf("DEBUG: S: %u E: %u B: %u traceFile: %s\n", S, E, B, traceFile);
        printf("DEBUG: setIndexMask: %llu\n", setIndexMask);
    #endif
    
    /* 重现追踪 */
    doTrace(traceFile);

    /* 销毁cache */
    freeCache();
    #ifdef USE_CACHELAB_H
        /* 输出hit, miss, eviction信息 */
        printSummary(hitCount, missCount, evictionCount);
    #endif
    return 0;
}
